package day02

import "sort"

// day02
//
// 1005. K 次取反后最大化的数组和
//
// https://leetcode.cn/problems/maximize-sum-of-array-after-k-negations/
//
// ```go
func largestSumAfterKNegations(nums []int, k int) int {
	sort.Slice(nums, func(i, j int) bool {
		return abs(nums[i]) > abs(nums[j])
	})
	for i := range nums {
		if k > 0 && nums[i] < 0 {
			nums[i] *= -1
			k--
		}
	}
	if k%2 == 1 {
		nums[len(nums)-1] *= -1
	}
	ans := 0
	for _, v := range nums {
		ans += v
	}
	return ans
}
func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}

// ```
//
// 134. 加油站
//
// https://leetcode.cn/problems/gas-station/
//
// ```go
func canCompleteCircuit(gas []int, cost []int) int {
	tot, sum, start := 0, 0, 0
	for i := 0; i < len(gas); i++ {
		tmp := gas[i] - cost[i]
		sum += tmp
		tot += tmp
		if sum < 0 {
			sum = 0
			start = i + 1
		}
	}
	if tot < 0 {
		return -1
	}
	return start
}

// ```
//
// 135. 分发糖果
//
// https://leetcode.cn/problems/candy/
//
// ```go
func candy(ratings []int) int {
	n := len(ratings)
	candys := make([]int, n)
	for i := range candys {
		candys[i] = 1
	}
	// 右 比 左
	for i := 1; i < n; i++ {
		if ratings[i] > ratings[i-1] {
			candys[i] = candys[i-1] + 1
		}
	}
	// 左比右
	for i := n - 2; i >= 0; i-- {
		if ratings[i] > ratings[i+1] {
			candys[i] = max(candys[i], candys[i+1]+1)
		}
	}
	ans := 0
	for _, v := range candys {
		ans += v
	}
	return ans
}

//```
